A communication network includes a collection of communicating devices (e.g., telephones, modems, computers, PDAs, video game consoles, routers, sensors) that can transmit and receive signals through a variety of communication media (e.g., wires, cables, air, water, space) for the purpose of delivering data (e.g., text, images, audio, video, sensor measurements) across space or time. There are a wide variety of communication networks in use today. These include, but are not limited to, traditional (wireline) telephone networks, wireless phone networks (e.g., cellular phone networks, satellite phone networks), local area networks (LANs), wide area networks (WANs), the Internet, cable television networks, RFID networks, and sensor networks.
There are many metrics used in characterizing the performance of a network. One common measure is the maximal data rate at which the network can deliver information. (Maximal data rates are sometimes described using terms such as the “network bandwidth,” “data bandwidth,” “information rate,” or “network capacity.” The term “bandwidth” in the context of data networks is typically used to quantify the amount of data delivered per unit of time. The term “capacity” is used to refer to the maximum possible data rate or collection of data rates that a link, path, or network can deliver per unit time). In other cases, it may be useful to describe the minimal distortions with which a network can deliver a collection of sources to their intended destinations, the latency or delay suffered in information delivery, the robustness of the network to component failures or adversarial attack, the extent to which information can be protected against eavesdropping, and so on. The metric of interest in analyzing a given network is often highly dependent on the application. For example, transmissions of live voice and video are far more sensitive to delay than is email, even when both data types travel through the same network.
Analyzing a network's performance is useful for a variety of applications. These include but are not limited to the following examples. Network users who wish to compare a variety of available networks can use network analysis to determine which network will give the best performance for their needs. Network designers interested in building new networks or reconfiguring old ones can use network analysis to optimize design choices with respect to relevant network metrics. Network analysis is also of potential use for guiding research and development. For example, by analyzing both metrics that provide theoretical bounds on a network's best possible performance and metrics that measure current performance using existing algorithms, researchers and entrepreneurs can distinguish between problems for which current solutions already achieve good performance and those where large gaps between theory and practice suggest a greater potential for advance. Network service providers can use network analysis to discover underlying structure in their networks, understand how much enabling a new service impacts existing services, inform pricing, guide network design, and improve network upgrades. Techniques for estimating network performance are also important for overlay network routing, traffic engineering, and capacity planning support.
Theoretical analysis of network performance is often extremely difficult. For example, the capacity of a single memoryless, noisy point-to-point channel is well-characterized, but the capacifies for many memoryless three-node networks (e.g., non-degraded broadcast and relay channels), most networks that can be built from memoryless, noisy point-to-point channels, and most channels with memory remain unsolved. A key challenge is that the capacities of a network's components do not necessarily determine the capacities of networks that can be built from those components. For example, consider a 4-node network in which node 1 transmits to nodes 2 and 3 through a broadcast channel and nodes 2 and 3 transmit to node 4 through a multiple access channel. Assume that the noise in the broadcast channel is independent of that in the multiple access channel. The capacity region for the complete network cannot be solved by combining the capacity regions of the two component channels. For example, the maximal rate at which node 1 can send information to node 4 is different when the broadcast channel is physically degraded than when the broadcast channel is stochastically degraded even though the capacity of the physically and stochastically degraded broadcast channels are identical.
One special family of networks for which the network capacity is relatively well-understood is the family of networks built from noiseless capacitated links (bit pipes). In these networks (bit-pipe networks) under some very structured connection types, network capacities are precisely characterized. For example, for multicast connections, where all messages start at a single node in the network and each receiver wishes to reconstruct all messages transmitted by that source node, the capacity is fully characterized for all network topologies. Unfortunately, finding capacities for general connection types remains a difficult problem. For example, the capacity of a network with a single multicast connection is solved, but the capacities of most networks with two or more multicast connections remain unsolved.
For the family of noiseless wireline networks under general connection types, information theoretic inequalities can be used to find outer bounds on network capacities. The linear outer bound described in R. W. Yeung, “A framework for linear information inequalities,” IEEE Transactions on Information Theory, 43(6):1924-1934, November 1997 (the disclosure of which is incorporated by reference herein in its entirety) gives the tightest outer bound implied by Shannon-type inequalities. This bounding technique has been implemented as the software programs Information Theoretic Inequalities Prover (ITIP) and XITIP. The program has complexity exponential in the number of links in the network and can thus only be used to compute capacity bounds for relatively small problem instances.
Since signals transmitted through real communication networks are corrupted by physical phenomena such as noise and attenuation, the tools for computing capacities of bit-pipe networks cannot be directly applied to compute capacities of real networks. As a result, the tools used to approximate the capacities of real networks are quite different from the tools described above. The tools used to study large networks are typically empirical, measuring achieved rate, available bandwidth, and bulk transfer capacity (BTC) across a single link or path. A network manager with administrative access to network routers and/or switches can measure bandwidth metrics by gathering data rate statistics at all accessible nodes (e.g., routers and switches). Since such access is typically available only to administrators and not to end users, end users can often only estimate the bandwidth of individual links or paths from end-to-end measurements. As a result, many such mechanisms yield only partial and unreliable assessments of a network's capacity.